#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 547. 省份数量.py
@time: 2022/3/4 18:28
@desc: https://leetcode-cn.com/problems/number-of-provinces/
> 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

1. 并查集，Ot(n2^logn), Os(n), 优秀题解：https://leetcode-cn.com/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/
'''


class UnionFind:
    def __init__(self):
        self.father = {}
        # 记录集合数量
        self.num_of_set = 0

    def find(self, x):
        # 查找x的祖先
        root = x
        # 注意应当写作self.father[root]==None, 因为有些结点为0
        while not self.father[root]==None:
            root = self.father[root]
        # 压缩路径
        while not x == root:
            origin_father = self.father[x]
            # 将当前的直接祖父都改成最上面的祖父
            self.father[x] = root
            x = origin_father

        return root

    def merge(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if not root_x == root_y:
            self.father[root_x] = root_y
            self.num_of_set -= 1

    def add(self, x):
        if x not in self.father:
            # 如果x的祖父还未有记录，就添加为空
            self.father[x] = None
            self.num_of_set += 1


class Solution:
    def findCircleNum(self, isConnected: list) -> int:
        uf = UnionFind()
        n = len(isConnected)
        for i in range(n):
            uf.add(i)
            for j in range(i):
                # 如果连通就合并
                if isConnected[i][j]:
                    uf.merge(i, j)
        return uf.num_of_set

if __name__ == '__main__':
    isConnected = [[1,1,1],[1,1,1],[1,1,1]]
    res = Solution().findCircleNum(isConnected)
    print(res)